package offer.binarytree;


import java.util.Arrays;
import java.util.List;

/**
 * Description：
 * Author: zhangc
 * Date：2017/8/15 22:51
 */
public class RebuildTree6 {

    public static <T extends Comparable<? super T>> BinaryTree<T> buildTree(T[] preOrder, T[] inOrder) {
        if (preOrder == null || preOrder.length <= 0)
            return null;
        return buildTree(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
    }

    public static <T extends Comparable<? super T>> BinaryTree<T> buildTree(T[] preOrder, int plow, int phigh, T[] inOrder, int ilow, int ihigh) {
        if (ilow > ihigh || plow > phigh)
            return null;
        BinaryTree<T> node = new BinaryTree<>(preOrder[ plow ]);
        for (int i = ilow; i <= ihigh; i++) {
            if (inOrder[ i ] == preOrder[ plow ]) {
                node.left = buildTree(preOrder, plow + 1, plow + i - ilow, inOrder, ilow, i - 1);
                node.right = buildTree(preOrder, i - ilow + plow + 1, phigh, inOrder, i + 1, ihigh);
            }
        }
        //int i = Arrays.binarySearch(inOrder, preOrder[ plow ]);

        return node;
    }

    public static void main(String[] args) {
        Integer[] preOrder = {1, 2, 4, 7, 3, 5, 6, 8};
        Integer[] inOrder = {4, 7, 2, 1, 5, 3, 6, 8};
        BinaryTree<Integer> tree = buildTree(preOrder, inOrder);
        List<Integer> list = tree.preOrder();
        for (Integer integer : list) {
            System.out.println(integer);
        }
    }

}
